package com.atguigu.method;

public class RecursionExercise2 {
    public static void main(String[] args) {
        for(int i=1; i<=10; i++){
            System.out.println(i +"级台阶共有几种走法：" +f(i));
        }
    }

    /*
    有n级台阶，一次只能上1步或2步，共有多少种走法？
    假设 f(n)代表 n级台阶的总走法
    f(1)  1
    f(2)  11                             2
    f(3)  111  21                        12
    f(4)  1111 211 121                   112 22
    f(5)  11111 2111 1211 1121 221       1112 212 122

    f(n) = f(n-1) + f(n-2)
     */
    public static int f(int n){
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        return f(n-1) + f(n-2);
    }
}
